package com.hr.leetcode.树和二叉树和二叉搜索树;

/**
 * @author 周恒哲
 * @date 2020/05/17
 **/
public class _235_二叉搜索树的最近公共祖先 {
    /**
     * 根据二叉排序树的性质，如果根节点大于去，q，p，则说明都在左子树上，反之都在右子树上，
     * 若大于p，小于q，则就是根节点
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        }

        return root;
    }

    //利用当前的节点是否等于根节点来判断
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (p.val == root.val || q.val == root.val) {
            return root;
        }
        TreeNode left = lowestCommonAncestor2(root.left, p, q);
        TreeNode right = lowestCommonAncestor2(root.right, p, q);
        /*if (left==null){
            return right;
        }
        if (right==null){
            return left;
        }
        if (left==null&&right==null){
            return root;
        }
        return root;*/
        //上面注释的可以用下面这一句概括
        return left == null ? right : right == null ? left : root;
    }
}
